#!/usr/bin/env perl

=head1 NAME

Google code jam

=cut

use strict;
use warnings;
use Text::CSV_XS;
use Data::Dumper;
use Log::Log4perl qw(:easy);
Log::Log4perl->easy_init(
						  {
							 level  => $INFO,
							 file   => ">B.log",
						  },
						  {
							 level  => $INFO,
							 file   => "STDOUT",
						  }
);

our ($T);
our @maps;

sub main() {
	load_data();
	write_output();
}

sub load_data() {
	my $filename = shift;
	my $csv = make_csv_parser();
	open my $fh_in, "<:utf8", "input.txt"
	  or LOGDIE("$!");
	
	my $row = $csv->getline ($fh_in);
	check_parser_for_errors( \$csv, \$row );
	$T = $row->[0] - 1;
	INFO("$T");
	
	#load maps
	for my $cur (0..$T){
		my $line = $csv->getline ($fh_in);
		$maps[$cur]->{H} = $line->[0] - 1;
		$maps[$cur]->{W} = $line->[1] - 1;
		INFO($cur . " H/W " . $maps[$cur]->{H} . " " . $maps[$cur]->{W});
		for my $row (0..$maps[$cur]->{H}){
			my $line = $csv->getline ($fh_in);
			for my $col (0..$maps[$cur]->{W}){
				$maps[$cur]->{matrix}->[$row]->[$col]->{alt} = $line->[$col];
			}
		}
	}

	close($fh_in);
}

sub write_output() {
	local $\ = "\n"; 
	
	open my $fh, ">:utf8", "output.txt" or LOGDIE "$!";
	
	for my $c (0..$T){
		INFO("Processing map $c");
		print $fh "Case #" . ($c + 1) . ":";
		my $map = $maps[$c];
		my @letters = split (/ /, "a b c d e f g h i j k l m n o p q r s t u v w x y z");
		for my $row (0..$map->{H}){
			my @labels;
			for my $col (0..$map->{W}){
				my $cell = $map->{matrix}->[$row]->[$col];
				# add neighbours
				my @neighbours;
				push @neighbours, $map->{matrix}->[$row-1]->[$col]
					if $row > 0;
				push @neighbours, $map->{matrix}->[$row]->[$col-1]
					if $col > 0;
				push @neighbours, $map->{matrix}->[$row]->[$col+1]
					if $col < $map->{W};
				push @neighbours, $map->{matrix}->[$row+1]->[$col]
					if $row < $map->{H};
				# find deepest
				my $min = $neighbours[0]->{alt};
				for my $neigh (@neighbours){
					$min = $neigh->{alt} 
						if $neigh->{alt} < $min;
				}
				# flow to the deepest if there is any
				if ($min < $cell->{alt}){
					for my $neigh (@neighbours){
						if ($neigh->{alt} == $min){
							if (defined $cell->{label}){
								$neigh->{label} = $cell->{label};	
							}
							elsif (defined $neigh->{label}){ # reverse flow
								$cell->{label} = $neigh->{label};	
							}
							else
							{
							    # do we have a label already? if not add one
								$cell->{label} = shift @letters;
								$neigh->{label} = $cell->{label};
							}
							last;
						}
					}
				}
				$cell->{label} = shift @letters # still no label? add one
					unless defined $cell->{label};
				push @labels, $cell->{label};
			}
			# write output
			print $fh join(' ', @labels);
		}

		
	}
	close $fh;
	INFO( 'DONE' );
}



sub make_csv_parser {
	my $csv = Text::CSV_XS->new(
		{
			sep_char    => qq{ },
			quote_char  => qq{"},    # default
			escape_char => qq{"},    # default
			binary      => 1,

			# modified settings below
			blank_is_undef     => 1,
			allow_loose_quotes => 1,
		}
	);
}

sub check_parser_for_errors {
	my ( $csv_ref, $row_ref ) = @_;
	if ( !( defined $$row_ref ) and !( $$csv_ref->eof() ) ) {
		my $bad_argument = $$csv_ref->error_input();    # get the most recent bad argument
		my $diag         = $$csv_ref->error_diag();
		print "WARNING: CSV parser error <$diag> on line - $bad_argument.\n";
	}
}

=back

=cut

=head1 AUTHOR

Tomasz Adamusiak 2009

=cut

main();
